
"""
104. 二叉树的最大深度
"""
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    def __init__(self):
        self.depth = 0
        self.max_depth = 0

    '''方法1，遍历二叉树'''
    def maxDepth1(self, root: Optional[TreeNode]) -> int:
        self.traverse1(root)
        return self.max_depth

    '''遍历二叉树'''
    def traverse1(self, root: Optional[TreeNode]):
        if not root:
            return
        # 前序位置
        self.depth += 1
        if not root.left and not root.right:
            self.max_depth = max(self.max_depth, self.depth)
        self.traverse1(root.left)
        # 中序位置
        self.traverse1(root.right)
        # 后序位置
        self.depth -= 1

    '''方法2，分解二叉树'''
    def maxDepth2(self, root: Optional[TreeNode]) -> int:
        return self.traverse2(root)

    '''遍历二叉树'''
    def traverse2(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        # 前序位置
        left = self.traverse2(root.left)
        # 中序位置
        right = self.traverse2(root.right)
        # 后序位置
        return max(left, right) + 1